#ifndef STRING_H_

#define STRING_H_

#include "status.h"
#include <iostream>
#include "stdlib.h"
using namespace std;

class String
{
private:
	char * str;
	int length;
	Status GetNext(const String & t, int * next) const;
public:
	String() : str(nullptr), length(0) {}
	String(char * ch);
	~String();
	Status StrCopy(const String & t);
	bool StrEmpty() const;
	int StrCompare(const String & t) const;
	int StrLength() const;
	Status ClearString();
	Status Concat(const String & s1, const String & s2);
	Status SubString(String & sub, int pos, int len) const;
	int Index(const String & t, int pos = 0) const;
	Status Replace(const String & t, const String & v);
	Status StrInsert(int pos, const String & t);
	Status StrDelete(int pos, int len);
	String & operator=(char * ch);
	String & operator=(const String & t);
	const char & operator[](int i) const ;
	char & operator[](int i);
	friend ostream & operator<<(ostream & os, const String & s);
};

ostream & operator<<(ostream & cout, const String & s)
{
	for (int i = 0; i < s.StrLength(); i++)
		cout << s[i];

	return cout;
}

String::String(char * ch)
{
	this->length = strlen(ch);
	this->str = new char[this->length];
	for (int i = 0; i < this->length; i++)
		this->str[i] = ch[i];
}

String::~String()
{
	delete[] this->str;
}

Status String::StrCopy(const String & t)
{
	if (!StrEmpty())
		delete[] this->str;
	this->length = t.StrLength();
	this->str = new char[this->length];
	for (int i = 0; i < this->length; i++)
	{
		this->str[i] = t[i];
	}

	return OK;
}

bool String::StrEmpty() const
{
	return this->length == 0;
}

int String::StrCompare(const String & t) const
{
	int len = this->length <= t.StrLength() ? this->length : t.StrLength();
	for (int i = 0; i < len; i++)
		if (this->str[i] != t[i])
			return this->str[i] - t[i];

	return this->length - t.StrLength();
}

int String::StrLength() const
{
	return this->length;
}

Status String::ClearString()
{
	if (StrEmpty())
		return ERROR;
	delete[] this->str;
	this->length = 0;

	return OK;
}

Status String::Concat(const String & s, const String & t)
{
	if (&s == this)
	{
		StrInsert(this->length, t);
		return OK;
	}

	if (!StrEmpty())
		delete[] this->str;

	this->length = s.StrLength() + t.StrLength();
	this->str = new char[this->length];
	int i;
	for (i = 0; i < s.StrLength(); i++)
		this->str[i] = s[i];
	for (int j = 0; j < t.StrLength(); j++, i++)
		this->str[i] = t[j];

	return OK;
}

Status String::SubString(String & sub, int pos, int len) const
{
	if (pos < 0 || len < 0 || pos + len > this->length)
		return ERROR;

	delete[] sub.str;
	sub.length = len;
	sub.str = new char[len];
	for (int i = 0; i < len; i++)
		sub[i] = this->str[pos + i];

	return OK;
}

//获取next数组
Status String::GetNext(const String & t, int * next) const
{
	int i = 0, j = -1;
	next[0] = -1;
	while (i < t.StrLength())
	{
		if (j == -1 || t[i] == t[j])
		{
			++i;
			++j;
			if (t[i] == t[j])
				next[i] = next[j];
			else
				next[i] = j;
		}
		else
			j = next[j];
	}

	return OK;
}

int String::Index(const String & t, int pos) const
{
	if (pos >= this->length || pos < 0)
		return -1;

	//获取子串t的next数组
	int * next = new int[t.StrLength()];
	GetNext(t, next);

	int i = pos;	//主串光标
	int j = 0;	//子串光标
	while (i < this->length)
	{
		if (j == -1 || this->str[i] == t[j])
		{
			++j;
			++i;
			if (j >= t.StrLength())
				return i - t.StrLength();
		}
		else
		{
			j = next[j];
		}
	}

	return -1;
}

Status String::Replace(const String & t, const String & v)
{
	int delLen = t.StrLength();
	int len = v.StrLength();

	int i = 0;
	int pos = Index(t, i);
	while (pos >= 0)
	{
		i = pos + len;
		this->StrDelete(pos, delLen);
		this->StrInsert(pos, v);
		pos = Index(t, i);
	}

	return OK;
}

Status String::StrInsert(int pos, const String & t)
{
	if (pos < 0 || pos > this->length)
		return ERROR;

	String tmp;
	tmp.StrCopy(*this);
	if (!StrEmpty())
		delete[] this->str;
	this->length += t.StrLength();
	this->str = new char[this->length];

	int i, j;
	for (i = 0, j = 0; i < pos; i++, j++)
	{
		this->str[j] = tmp[i];
	}
	for (; j < pos + t.StrLength(); j++)
	{
		this->str[j] = t[j - pos];
	}
	for (; i < tmp.StrLength(); i++, j++)
	{
		this->str[j] = tmp[i];
	}

	return OK;
}

Status String::StrDelete(int pos, int len)
{
	if (pos < 0 || len < 0 || pos + len > this->length)
		return ERROR;

	String tmp;
	tmp.StrCopy(*this);

	if (!StrEmpty())
		delete[] this->str;
	this->length -= len;
	this->str = new char[this->length];

	int j = 0;
	for (int i = 0; i < tmp.StrLength(); i++)
	{
		if (i < pos || i >= pos + len)
		{
			this->str[j] = tmp[i];
			++j;
		}
	}

	return OK;
}

String & String::operator=(char * ch)
{
	if (!StrEmpty())
		delete[] this->str;
	this->length = strlen(ch);
	this->str = new char[this->length];
	for (int i = 0; i < this->length; i++)
		this->str[i] = ch[i];

	return *this;
}

String & String::operator=(const String & t)
{
	if (!StrEmpty())
		delete[] this->str;
	this->length = t.StrLength();
	this->str = new char[this->length];
	for (int i = 0; i < this->length; i++)
		this->str[i] = t[i];

	return *this;
}

char & String::operator[](int i)
{
	return this->str[i];
}

const char & String::operator[](int i) const
{
	return this->str[i];
}

#endif




